package airthmetic.exercise.dp;

// 经典dp的0-1背包问题
//1.1、问题描述
//      给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 wt[i]，价值为 v[i]。
//      现在让你用这个背包装物品，每种物品可以选0个或1个，问最多能装的价值是多少？
public class BackPack5 {


    /**
     *
     * @param wt 每个物品的重量 即wt[i]是第i个物品的重量
     * @param v  每个物品的价值 即v[i]是第i个物品的价值
     * @param N  物品个数
     * @param W  背包重量
     * @return 最多能装多少价值
     */
    public static int dp(int[] wt, int[] v, int N, int W) {
        /**
         * 1.确定状态参数和选择
         *      状态参数：W背包容量 N物品数量
         *      选择/决策: 选择不同的背包重量和物品数量
         *
         * 2.定义dp table
         *  int[][] dp = new int[N][W];
         *  dp[i][j] 表示 前i个物品 j重量的背包最多装多少价值
         *
         * 3.初始化 dp table
         *  当背包重量为0时 不管前多少个物品装出的价值都是0
         *  当物品个数为0时 不管背包有多少容量装出来的价值都是0
         *
         * 4.推导状态转移公式
         *    当当前物品重量大于背包容量   从当前容量，前一个物品转移过来
         *    当当前物品重量小于等于背包容量 从前一个物品,当前背包容量-当前物品重量的最多能装价值 + 当前物品价值  和 dp[i-1][j] 中的最大值转移过来(因为dp[i-1][j]是不装当前物品的价值，不装当前物品可以装以前的其他物品，以前的其他物品价值可能是更高的)
         *    for(int i=1; i<=N; i++){
         *        for(int j=1; j<=W; j++){
         *            if(wt[i-1] > j){
         *               dp[i][j] = dp[i-1][j];
         *            }else{
         *                dp[i][j] = Math.max(dp[i-1][j - wt[i-1]] + v[i-1] , dp[i][j]);
         *            }
         *        }
         *    }
         */


        int[][] dp = new int[N+1][W+1];
        for(int i=1; i<=N; i++){
            for(int j=1; j<=W; j++){
                if(wt[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j - wt[i-1]] + v[i-1] , dp[i-1][j]);
                }
            }
        }

        return dp[N][W];

    }

    public static void main(String[] args) {
        int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
        int[] wt = {3, 2, 1}; // 物品的重量
        int[] v = {5, 2, 3}; // 物品的价值
        System.out.println(new BackPack().dp(wt,v,N,W));
    }
}

